package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: jeason
 * @Description: 输入一个表达式（用字符串表示），求这个表达式的值。
 * 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
 * @Date: 2021/4/4 18:12
 */
public class Arithmetic {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String line = null;
        while ((line = bufferedReader.readLine()) != null){
            System.out.println(infixToSuffix(line));
            System.out.println(calSuffix(infixToSuffix(line)));
        }
    }
    private static int youxianjishu(char aChar){
        if (aChar == '}' || aChar == ']' || aChar == ')'){
            return 4;
        }
        if (aChar == '{' || aChar == '[' || aChar == '('){
            return 1;
        }
        if (aChar == '*' || aChar == '/'){
            return 3;
        }
        if (aChar == '+' || aChar == '-'){
            return 2;
        }
        return 0;
    }

    private static String infixToSuffix(String s){
        char[] chars = s.toCharArray();
        char[] stack = new char[s.length()];
        int index = -1;
        StringBuilder stringBuilder = new StringBuilder();
        int start, end;
        for (int i=0;i<chars.length;i++) {
            char aChar = chars[i];
            //数字：直接添加至后缀表达式
            if (aChar >= '0' && aChar <= '9'){
                start = i;
                while (i+1 <chars.length && chars[i+1] >= '0' && chars[i+1] <= '9'){
                    i++;
                }
                end = i;
                aChar = (char) (Integer.parseInt(s.substring(start,end+1)) + '0');
                stringBuilder.append(aChar);
                continue;
            }

            //左括号：直接入栈
            if (aChar == '{' || aChar == '[' || aChar == '('){
                stack[++index] = aChar;
                continue;
            }
            //右括号：不入栈，栈内第一个左括号前端运算符出栈添加至后置表达式后面，左括号出栈
            if (aChar == '}' || aChar == ']' || aChar == ')'){
                while (index >= 0 && stack[index] != '{' && stack[index] != '[' && stack[index] != '('){
                    stringBuilder.append(stack[index--]);
                }
                index--;
                continue;
            }
            //运算符：若栈为空，直接入栈，否则和栈顶运算符比较优先级，栈顶大于等于此运算符则弹出栈顶元素，并继续判断，直至不满足上述条件或栈为空，则直接入栈
            if (aChar == '*' || aChar == '/' || aChar == '+' || aChar == '-'){
                if (i == 0){
                    stringBuilder.append('0');
                }
                if (chars[i-1] == '{' || chars[i-1] == '[' || chars[i-1] == '('){
                    stringBuilder.append('0');
                }
                if (index < 0){
                    stack[++index] = aChar;
                    continue;
                }
                while (index >=0 && youxianjishu(aChar) <= youxianjishu(stack[index])){
                    stringBuilder.append(stack[index--]);
                }
                stack[++index] = aChar;
            }
        }
        while (index >= 0){
            stringBuilder.append(stack[index--]);
        }
        return stringBuilder.toString();
    }

    private static int calSuffix(String s){
        char[] chars = s.toCharArray();
        int[] stack = new int[chars.length];
        int head = -1;
        for (char aChar : chars) {
            if (aChar == '*' || aChar == '/' || aChar == '+' || aChar == '-'){
                int b = stack[head--];
                int a = stack[head--];
                int c = cal(a,b,aChar);
                stack[++head] = c;
            }else {
                stack[++head] = aChar - '0';
            }
        }
        return stack[head];
    }

    private static int cal(int a,int b,char o){
        if (o == '+'){
            return a + b;
        }
        if (o == '-'){
            return a - b;
        }
        if (o == '*'){
            return a * b;
        }
        if (o == '/'){
            return a / b;
        }
        return 0;
    }

}
